ডিসজয়েন্ট সেট ইউনিয়ন (Union-Find Algorithm) বা ইউনিয়ন-ফাইন্ড ডেটা স্ট্রাকচার একটি গুরুত্বপূর্ণ অ্যালগরিদম যা সেটগুলির মধ্যে ঐক্য এবং প্রতিনিধিত্ব পরিচালনার জন্য ব্যবহৃত হয়। এটি সাধারণত গ্রাফ থিওরি, নেটওয়ার্কিং, এবং কম্পিউটেশনাল জ্যামিতির ক্ষেত্রে সমষ্টির সমস্যা সমাধানে ব্যবহৃত হয়, যেমন সাইকেল শনাক্তকরণ এবং সংযোগকারী উপগ্রাফ তৈরি করতে।
মূল বৈশিষ্ট্য
- নতুন সেট তৈরি: নতুন সেট তৈরি করা।
- একত্রিত (Union): দুইটি সেটকে একত্রিত করা।
- প্রতিনিধি (Find): একটি উপাদান কোন সেটের অন্তর্ভুক্ত তা নির্ধারণ করা।
ডেটা স্ট্রাকচার
ডিসজয়েন্ট সেট ইউনিয়ন সাধারণত দুটি প্রধান উপাদান নিয়ে কাজ করে:
- প্যারেন্ট অ্যারে (Parent Array): প্রতিটি উপাদান কোন সেটের অন্তর্গত তা বোঝাতে ব্যবহৃত হয়। এটি প্রতিটি উপাদানের প্যারেন্টকে নির্দেশ করে।
- র্যাঙ্ক (Rank): এটি প্রায়শই একটি সেটের উচ্চতা সংরক্ষণ করে যাতে ইউনিয়ন অপারেশনগুলি দক্ষ হয়।
অ্যালগরিদমের কাজের পদ্ধতি
ডিসজয়েন্ট সেট ইউনিয়ন সাধারণত দুটি প্রধান অপারেশন নিয়ে কাজ করে:
১. Find Operation
এই অপারেশনটি একটি উপাদানের প্যারেন্ট বা প্রতিনিধিকে খুঁজে বের করে। এটি রিকারসিভ বা iterative পদ্ধতিতে করা যেতে পারে। এটি সাধারণত পাথ কম্প্রেশন (path compression) ব্যবহার করে কার্যকরী হয়, যা ভবিষ্যতে খোঁজার সময়কে হ্রাস করে।
উদাহরণ:
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x]) # Path compression
return parent[x]
২. Union Operation
এই অপারেশনটি দুটি সেটকে একত্রিত করে। এটি সাধারণত র্যাঙ্ক বা সাইজ ব্যবহার করে কার্যকরী হয়, যাতে সর্বনিম্ন উচ্চতার গাছ তৈরি করা যায় এবং কর্মক্ষমতা বৃদ্ধি পায়।
উদাহরণ:
def union(parent, rank, x, y):
root_x = find(parent, x)
root_y = find(parent, y)
if root_x != root_y:
if rank[root_x] > rank[root_y]:
parent[root_y] = root_x
elif rank[root_x] < rank[root_y]:
parent[root_x] = root_y
else:
parent[root_y] = root_x
rank[root_x] += 1
সম্পূর্ণ উদাহরণ (পাইথনে):
class DisjointSetUnion:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
if self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
elif self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
# ব্যবহার
dsu = DisjointSetUnion(5)
# একত্রিত করা
dsu.union(0, 1)
dsu.union(1, 2)
print(dsu.find(0)) # আউটপুট: 0 (0 এর প্রতিনিধি)
print(dsu.find(1)) # আউটপুট: 0 (1 এর প্রতিনিধি)
print(dsu.find(2)) # আউটপুট: 0 (2 এর প্রতিনিধি)
# নতুন একত্রিত করা
dsu.union(3, 4)
print(dsu.find(3)) # আউটপুট: 3 (3 এর প্রতিনিধি)
সময় জটিলতা
ডিসজয়েন্ট সেট ইউনিয়নের কাজের সময় জটিলতা:
- Find: O(α(n)), যেখানে α হল অ্যাক্সেসর ফাংশন।
- Union: O(α(n))
উপসংহার
ডিসজয়েন্ট সেট ইউনিয়ন একটি কার্যকরী এবং মৌলিক ডেটা স্ট্রাকচার যা সেটগুলির মধ্যে সম্পর্ক পরিচালনার জন্য ব্যবহৃত হয়। এটি বিভিন্ন সমস্যার সমাধানে, যেমন গ্রাফ অ্যালগরিদম, সাইকেল শনাক্তকরণ এবং অন্যান্য সমস্যা সমাধানে কার্যকরী। পাথ কম্প্রেশন এবং র্যাঙ্ক ব্যবহার করে এটি খুব কার্যকরীভাবে কাজ করে।
